package com.algorithms.sorts;

/**
 * SelectionSort take the complexity O(N^2)<br>
 * Similar to the BubbleSort but reduces the number of swaps<br><br>
 * 
 * we go from the smallest index of array, we try to find the smallest 
 * item and place it to that index. then we move forward to the next
 * index and find the next smallest one.<br><br>
 * 
 * by this algorithm, it is similar to the <b>BubbleSort</b> but we can
 * reduce the number of swaps. we only swap when we found the smallest
 * item.
 * 
 * 
 * @author minhld
 *
 */
public class SelectionSort extends Sort{
	
	public SelectionSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "SelectionSort";
	}
	
	@Override
	public int[] sort(){
		int min, minIndex = -1;
				
		for (int i = 0; i < this.length; i++){
			min = this.data[i];
			minIndex = i;
			
			// searching for the minimum value in the rest of array
			for (int j = i; j < this.length; j++){
				if (this.data[j] < min){
					min = this.data[j];
					minIndex = j;
					
					this.numOfCopy++;
				}
				
				this.numOfProcess++;
			}
			
			// switch data[i] and data[minIndex]
			if (minIndex != i){
				swap(i, minIndex);
				
				this.numOfCopy += 2;
			}
			
			this.numOfProcess++;
		}
		
		return this.data;
	}
}
